package DataStructure.tree.binaryTree.binaryTreeApply;

import Common.Utils.UTFactory;
import DataStructure.tree.binaryTree.BinaryTreeImpl;
import org.junit.Test;

import java.util.*;

/**
 * @author 蔚蔚樱
 * @version 1.0
 * @date 2020/8/19
 * @author—Email micromicrohard@outlook.com
 * @blogURL https://leetcode-cn.com/problems/maximum-width-of-binary-tree/
 * @description 二叉树最大深度
 */
public class BT_MaxDepth {

    @Test // 验证功能：从数据库获取测试数据，用于单元测试
    public void TestFunc() throws Exception {
        UTFactory.FullTest(this.getClass());
    }

    @Test // 调试功能 : 用于复现错误的测试案例
    public void DoubleTrack() throws Exception {
        String input = "";
        String output = "";
        UTFactory.DebugTest(this.getClass(), input, output);
    }

    Map<BinaryTreeImpl, Integer> statisticsMap = new HashMap<>();

    // 获取树的最大深度
    public int getMaxDepthMethod(BinaryTreeImpl root) {
        if (root == null) {
            return 0;
        }
        int left = getMaxDepthMethod(root.left);
        int right = getMaxDepthMethod(root.right);
        statisticsMap.put(root, Math.max(left, right) + 1);
        return statisticsMap.get(root);
    }

    public int getMaxDepthMethodByQueue(BinaryTreeImpl root) {
        if (root == null) {
            return 0;
        }
        statisticsMap = new HashMap<>();
        Queue<BinaryTreeImpl> queue = new LinkedList<>();
        queue.offer(root);
        int level = 1;
        BinaryTreeImpl head = root;
        BinaryTreeImpl tail = root;
        statisticsMap.put(root, level);
        while (!queue.isEmpty()) {
            BinaryTreeImpl cur = queue.poll();
            if (cur.left != null) {
                queue.offer(cur.left);
                tail = cur.left;
                statisticsMap.put(cur.left, level + 1);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
                tail = cur.right;
                statisticsMap.put(cur.left, level + 1);
            }
            if (cur.equals(head)) {
                head = tail;
                level++;
            }
        }
        level--; // 减去最后一次多加的层数
        // 通过遍历的方式：重新梳理层高值
        for (BinaryTreeImpl node : statisticsMap.keySet()) {
            int tempLevel = statisticsMap.get(node);
            statisticsMap.put(node, level - tempLevel + 1);
        }
        return statisticsMap.get(root);
    }
}
